import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ling
 * Date: 2022-04-30
 * Time: 10:32
 */
public class MySingleList {
    static class ListNode{
        public int val;//数据域
        public ListNode next;//指针域
        public ListNode(int val){
            this.val=val;
        }
    }
    public ListNode head;//代表单链表的头结点的引用
    public int size;
    //头插法
    public void addFirst(int data){
     ListNode node=new ListNode(data);
//     if(this.head==null){
//         this.head=node;
//     }else{
//         node.next=this.head;
//         this.head=node;
//     }
        node.next=this.head;
        this.head=node;
        this.size++;
 }
  //尾插法
  public void addLast(int data){
      ListNode node=new ListNode(data);
      if(this.head==null){
          this.head=node;
      }else{
          ListNode cur=head;
          while(cur.next!=null){
              cur=cur.next;
          }
          cur.next=node;
      }
      this.size++;
    }
    private ListNode findIndexFront(int index){
        ListNode cur=head;
        while(index-1!=0){
            cur=cur.next;
            index--;
        }
        return cur;
    }
  //任意位置插入,第一个数据节点为0号下标
  public boolean addIndex(int index,int data){
       if(index<0||index>=this.size){
           throw new MySingleListIndexOutOfException("输入参数错误");
       }
       if(index==0){
           addFirst(data);
           this.size++;
           return true;
       }else if(index==this.size-1){
           addLast(data);
           this.size++;
           return true;
       }else{
           ListNode cur=findIndexFront(index);
           ListNode newNode=new ListNode(data);
           newNode.next=cur.next;
           cur.next=newNode;
           this.size++;
           return true;
       }
    }
  //查找是否包含关键字key是否在单链表当中
  public boolean contains(int key){
       if(head==null){
           return false;
       }else{
           ListNode cur=head;
           while(cur!=null){
               if(cur.val==key){
                   return true;
               }
               cur=cur.next;
           }
           return false;
       }
  }
    private ListNode findKeyFront(int key){
        ListNode cur=head;
        while(cur.next!=null){
            if(cur.next.val==key){
                return cur;
            }
            cur=cur.next;
        }
        return null;
    }
    private ListNode removeFist(){
        ListNode cur=this.head;
        this.head=this.head.next;
        cur.next=null;
        return head;
    }
  //删除第一次出现关键字为key的节点
  public void remove(int key){
        if(head==null)
            return ;
        ListNode cur=head;
        if(cur.val==key){
            removeFist();
            this.size--;
        }else{
            cur=findKeyFront(key);
            if(cur==null)
                return;
            cur.next=cur.next.next;
            this.size--;
        }

  }
         //删除所有值为key的节点
    public void removeAllKey(int key){
        if(this.head==null){
            return ;
        }else{
            ListNode cur=head;
            while(cur!=null){
                if(cur.val==key){
                   cur=removeFist();
                   this.size--;
                }else{
                    cur=findKeyFront(key);
                    if(cur==null)
                        return;
                    cur.next=cur.next.next;
                    this.size--;
                }
            }
        }
          }
  //得到单链表的长度
  public int size(){
        return this.size;
         }

    public void display(){
       if(head==null){
           return ;
       }else{
           ListNode cur=head;
           while(cur!=null){
               System.out.print(cur.val+" ");
               cur=cur.next;
           }
       }
  }
    public void clear() {
        ListNode cur=this.head;
        while(cur!=null){
            head=head.next;
            cur.next=null;
            cur=head;
            System.gc();
        }
    }

}
